Computer programs are widely used by businesses to access databases for performing business transactions, such as making a savings account deposit or a withdrawal, reserve or purchase an airline ticket, buy or sell a security, etc. Each of these business transactions rely on the integrity of the data in the databases, i.e. the balance in the savings account must reflect the correct amount after the deposit or withdrawal. However, the databases described in the business transactions above are generally accessed and modified by multiple concurrently run computer programs. These concurrently run programs interleave their access to databases, which may result in one program's database access interfering with another program's access to the same database. Such interferences may result in erroneous data in the databases.
Protocols exist presently to avoid such database errors caused by interfering programs. One such protocol is a static two-phase locking scheme. In a transaction including a plurality of steps, for example, some steps access at least one data item in a database. The static two-phase locking scheme would provide for "locking" all the data items to be accessed, before any step in the transaction is performed, to prevent any other transactions from accessing and altering the data items. The data items are "unlocked" immediately following the last step of the transaction.
A similar protocol, dynamic two-phase locking scheme, locks each data item to be accessed by the transaction immediately prior to each accessing step, and then releases the locks on all the data items immediately following the last step of the transaction.
Both the static and dynamic two-phase locking scheme exhibit a first phase, during which locks are acquired on required data items, and a second phase, during which all the locks are released. By locking the data items, a form of scheduling is achieved, since only the programs that have locked all of their required data items are executed to completion. Other programs which have not acquired locks on all of their data items, because at least one is locked by another program, must wait. In other words, the locking scheme in effect puts concurrently run programs in serial execution form.
A problem arising from the two-phase locking scheme is the reduction in program execution throughput. For example, if access of data item A is required by transactions X and Y, and transaction X has a lock on data item A. Since the lock on data item A will not be released until the completion of the very last step of transaction X, transaction Y must wait until the end of transaction X even though the transaction X step associated with data item A may have long been completed. Therefore, from the foregoing it may be seen that the concurrency of the programs is not fully exploited to achieve high throughput when two-phase locking is employed.
There often exists one data item that every transaction must access, such as a history database that records all transactions. By using the two-phase locking scheme, a bottleneck or hot spot is created at that data item, since every transaction must wait for the transaction that currently has the lock on that data item to complete. Therefore, hot spot detection and special handling are needed in a two-phase locking scheme, so that the blocked transactions do not need to wait the entire duration of the transaction which currently has a lock on the hot data item.
Another protocol used to serialize database transactions is the tree and path protocol. In the tree and path protocols, the data items must be accessed following an inherent and specific sequence. The predictable access behavior is exploited by the tree and path protocols to serialize data item access. A data item in a tree or path structure may be locked and accessed, and the data item following it in sequence is then locked before releasing the lock on the previous data item. Although the tree and path protocols are not two-phased, and therefore do not have the reduced throughput problem described above, these protocols are only applicable to those databases which are accessible only in a predetermined order. Therefore, the tree and path protocols are ineffective for data items which do not have an inherent access order.
Accordingly, a need has arisen for a locking scheme that more fully exploits the concurrency of multiple transactions to increase throughput, and which does not rely on the inherent order of the data.